package collections

import "fmt"

// 二叉树实现

type Node struct {
	Value int
	Left  *Node
	Right *Node
}

// 树的前序遍历，递归实现
func (n *Node) PreOrder(res *[]int) {
	if n == nil {
		return
	}
	*res = append(*res, n.Value)
	n.Left.PreOrder(res)
	n.Right.PreOrder(res)
}

// 中序遍历
func (n *Node) MidOrder(res *[]int) {
	if n == nil {
		return
	}
	n.Left.PreOrder(res)
	*res = append(*res, n.Value)
	n.Right.PreOrder(res)
}

// 后序遍历
func (n *Node) AfterOrder(res *[]int) {
	if n == nil {
		return
	}
	n.Left.PreOrder(res)
	n.Right.PreOrder(res)
	*res = append(*res, n.Value)
}

// 广度优先遍历
func (n *Node) DeepTraversal() {
	if n == nil {
		return
	}

	// 充当队列
	Q := make([]*Node, 0)
	res := make([]int, 0)
	Q = append(Q, n)
	for len(Q) > 0 {
		cur := Q[0]
		Q = Q[1:] // 出队
		res = append(res, cur.Value)
		if cur.Left != nil {
			Q = append(Q, cur.Left)
		}

		if cur.Right != nil {
			Q = append(Q, cur.Right)
		}
	}
	PrintResult(res, "DeepTraversal")
}

// 深度优先遍历
func (n *Node) BreadthTraversal() {
	if n == nil {
		return
	}

	Stack := make([]*Node, 0)
	res := make([]int, 0)

	Stack = append(Stack, n)

	for len(Stack) > 0 {
		cur := Stack[len(Stack)-1] // 最后一个元素
		Stack = Stack[:len(Stack)-1]
		res = append(res, cur.Value)

		if cur.Right != nil {
			Stack = append(Stack, cur.Right)
		}

		if cur.Left != nil {
			Stack = append(Stack, cur.Left)
		}

	}

	PrintResult(res, "BreadthTraversal")
}

// 树的遍历
func TreeTraversal() {
	root := testData()

	res := make([]int, 0)
	root.PreOrder(&res)
	PrintResult(res, "PreOrder")

	res = make([]int, 0)
	root.MidOrder(&res)
	PrintResult(res, "MidOrder")

	res = make([]int, 0)
	root.AfterOrder(&res)
	PrintResult(res, "AfterOrder")

	root.DeepTraversal()

	root.BreadthTraversal()
}

func PrintResult(arr []int, order string) {
	fmt.Print(order + ": ")
	for _, v := range arr {
		fmt.Printf("%2d", v)
	}
	fmt.Println()
}

func testData() *Node {
	root := Node{Value: 0}

	root.Left = &Node{Value: 1}
	root.Right = &Node{Value: 2}

	root.Left.Left = &Node{Value: 3}
	root.Left.Right = &Node{Value: 4}

	root.Left.Left.Right = &Node{Value: 5}

	root.Right.Right = &Node{Value: 6}
	return &root
}
